#ifndef S21_CONTAINER_LIST_H_
#define S21_CONTAINER_LIST_H_

#include <initializer_list>

#include "s21_list_const_iterator.h"
#include "s21_list_iterator.h"
#include "s21_list_node.h"

namespace s21 {

template <typename T>
class list {
 public:
  using value_type = T;
  using reference = value_type&;
  using const_reference = const value_type&;
  using rv_reference = value_type&&;
  using iterator = Iterator<value_type>;
  using const_iterator = ConstIterator<value_type>;
  using size_type = std::size_t;

  list() : fake_(alloc.allocate(1)), size_(0) {
    fake_->next = fake_;
    fake_->prev = fake_;
  }

  explicit list(size_type n) : list() {
    while (size_ < n) {
      push_back(value_type());
    }
  }

  list(std::initializer_list<value_type> const& items) : list() {
    for (auto it = items.begin(); it != items.end(); ++it) {
      push_back(*it);
    }
  }

  list(const list& other) : list() {
    for (auto it = other.cbegin(); it != other.cend(); ++it) {
      push_back(*it);
    }
  }

  list(list&& other) noexcept : fake_(other.fake_), size_(other.size_) {
    other.fake_ = nullptr;
    other.size_ = 0;
  }

  ~list() {
    if (fake_) {
      clear();
      alloc.deallocate(fake_, 1);
    }
  }

  list& operator=(const list& other) {
    if (this != &other) {
      list tmp{other};
      swap(tmp);
    }

    return *this;
  }

  list& operator=(list&& other) noexcept {
    if (this != &other) {
      list tmp{std::move(other)};
      swap(tmp);
    }

    return *this;
  }

  const_reference front() const { return fake_->next->value; }

  const_reference back() const { return fake_->prev->value; }

  iterator begin() { return iterator{fake_->next}; }

  iterator end() { return iterator{fake_}; }

  const_iterator cbegin() const { return const_iterator{fake_->next}; }

  const_iterator cend() const { return const_iterator{fake_}; }

  bool empty() const noexcept { return size_ == 0; }

  size_type size() const noexcept { return size_; }

  size_type max_size() const { return SIZE_MAX / sizeof(Node<value_type>); }

  void clear() {
    for (Node<value_type>*i = fake_->next, *tmp = i; i != fake_; i = tmp) {
      tmp = i->next;
      delete_node(i);
    }

    fake_->next = fake_;
    fake_->prev = fake_;
    size_ = 0;
  }

  iterator insert(iterator pos, const_reference value) {
    Node<value_type>* node = create_node(value);
    integrate_node(pos.node_, node);
    iterator result{node};

    return result;
  }

  iterator insert(iterator pos, rv_reference value) {
    Node<value_type>* node = create_node(std::move(value));
    integrate_node(pos.node_, node);
    iterator result{node};

    return result;
  }

  void erase(iterator pos) { delete_node(isolate_node(pos.node_)); }

  void push_back(const_reference value) {
    Node<value_type>* node = create_node(value);
    integrate_node(fake_, node);
  }

  void push_back(rv_reference value) {
    Node<value_type>* node = create_node(std::move(value));
    integrate_node(fake_, node);
  }

  void pop_back() { delete_node(isolate_node(fake_->prev)); }

  void push_front(const_reference value) {
    Node<value_type>* node = create_node(value);
    integrate_node(fake_->next, node);
  }

  void push_front(rv_reference value) {
    Node<value_type>* node = create_node(std::move(value));
    integrate_node(fake_->next, node);
  }

  void pop_front() { delete_node(isolate_node(fake_->next)); }

  void swap(list& other) noexcept {
    std::swap(fake_, other.fake_);
    std::swap(size_, other.size_);
  }

  void merge(list& other) {
    if (this == &other || other.empty()) return;

    for (Node<value_type>* i = fake_->next; i != fake_ && other.size_ > 0;
         i = i->next) {
      for (Node<value_type>*j = other.fake_->next, *tmp = j;
           j != other.fake_ && j->value < i->value; j = tmp) {
        tmp = j->next;
        integrate_node(i, other.isolate_node(j));
      }
    }

    splice(cend(), other);
  }

  void splice(const_iterator pos, list& other) {
    if (this == &other || other.empty()) return;

    pos.node_->prev->next = other.fake_->next;
    other.fake_->next->prev = pos.node_->prev;
    other.fake_->prev->next = pos.node_;
    pos.node_->prev = other.fake_->prev;
    size_ += other.size_;

    other.fake_->next = other.fake_;
    other.fake_->prev = other.fake_;
    other.size_ = 0;
  }

  void reverse() {
    for (Node<value_type>* i = fake_->next; i != fake_; i = i->prev) {
      std::swap(i->next, i->prev);
    }

    std::swap(fake_->next, fake_->prev);
  }

  void unique() {
    for (Node<value_type>*i = fake_->next, *j = i->next; j != fake_;
         j = i->next) {
      if (i->value == j->value) {
        delete_node(isolate_node(j));
      } else {
        i = i->next;
      }
    }
  }

  void sort() {
    if (size_ <= 1) return;

    if (size_ == 2) {
      if (fake_->prev->value < fake_->next->value) {
        reverse();
      }

      return;
    }

    list other;

    for (size_type i = size_ / 2; i > 0; --i) {
      Node<value_type>* node = fake_->prev;
      other.integrate_node(other.fake_, isolate_node(node));
    }

    sort();
    other.sort();

    merge(other);
  }

  template <typename... Args>
  iterator insert_many(const_iterator cpos, Args&&... args) {
    iterator tmp{cpos.node_->prev};
    iterator pos{cpos.node_};
    (insert(pos, std::forward<Args>(args)), ...);
    ++tmp;

    return tmp;
  }

  template <typename... Args>
  void insert_many_back(Args&&... args) {
    iterator pos{fake_};
    (insert(pos, std::forward<Args>(args)), ...);
  }

  template <typename... Args>
  void insert_many_front(Args&&... args) {
    iterator pos{fake_->next};
    (insert(pos, std::forward<Args>(args)), ...);
  }

 private:
  Node<value_type>* fake_;
  size_type size_;
  std::allocator<Node<value_type>> alloc;

  Node<value_type>* create_node(const_reference value) {
    Node<value_type>* node = alloc.allocate(1);
    alloc.construct(node, value);

    return node;
  }

  Node<value_type>* create_node(rv_reference value) {
    Node<value_type>* node = alloc.allocate(1);
    alloc.construct(node, std::move(value));

    return node;
  }

  void delete_node(Node<value_type>* node) {
    alloc.destroy(node);
    alloc.deallocate(node, 1);
  }

  void integrate_node(Node<value_type>* pos, Node<value_type>* node) {
    node->prev = pos->prev;
    node->next = pos;
    pos->prev->next = node;
    pos->prev = node;
    ++size_;  // only here
  }

  Node<value_type>* isolate_node(Node<value_type>* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    --size_;  // only here

    return node;
  }
};
}  // namespace s21
#endif  // S21_CONTAINER_LIST_H_